package leetCode;

import java.util.*;

public class t76 {
    public static void main(String[] args) {

        System.out.printf(Solution.minWindow("a", "aa"));
    }
    static class Solution {
        static Map<Character, Integer> ori = new HashMap<Character, Integer>();
        static Map<Character, Integer> cnt = new HashMap<Character, Integer>();



        public static String minWindow(String s, String t) {
            for (int i=0;i<t.length();i++){
                char c = t.charAt(i);
                if (ori.containsKey(c)){
                    ori.put(c,ori.get(c)+1);
                }else {
                    ori.put(c,1);
                }

            }
            int lIndex=0;
            int rIndex=0;
            String minStr="";
            int minCount=Integer.MAX_VALUE;
            while (rIndex<s.length()){
                if (cnt.containsKey(s.charAt(rIndex))){
                    cnt.put(s.charAt(rIndex),cnt.get(s.charAt(rIndex))+1);
                }else {
                    cnt.put(s.charAt(rIndex),1);
                }

                while(check()){
                    if (rIndex-lIndex<minCount){
                        minCount=rIndex-lIndex;
                        minStr=s.substring(lIndex,rIndex+1);
                    }
                    if (cnt.containsKey(s.charAt(lIndex))){
                        if (cnt.get(s.charAt(lIndex))!=0){
                            cnt.put(s.charAt(lIndex),cnt.get(s.charAt(lIndex))-1);
                        }
                    }

                    lIndex++;
                }
                rIndex++;
            }

            return minStr;
        }
        public static boolean check(){
            Set<Character> characters = ori.keySet();
            Iterator<Character> iterator = characters.iterator();
            while(iterator.hasNext()){
                Character next = iterator.next();
                if (!cnt.containsKey(next)){
                    return false;
                }
                if (ori.get(next)>cnt.get(next)){
                    return false;
                }
            }
            return true;
        }
    }
}
